#include "fieldgenerator.h"
#include "Bot.h"
#include "Logger.h"
#include <math.h>
#include <functional>
#include <map>
#include <queue>
#include <cfloat>

using namespace std;

//constructor
Bot::Bot():field(state)
{

};

//plays a single game of Ants.
void Bot::playGame()
{
    //reads the game parameters and sets up
    Logger::theLogger() << "Reading initial state" << endl;
    cin >> state;
    state.setup();
    endTurn();
    field.initField();
    Logger::theLogger() << "Turn 0 completed" << endl;

    //continues making moves while the game is not over
    while(cin >> state)
    {
	Logger::theLogger() << "Starting updateVision" << endl;
        state.updateVisionInformation();
	Logger::theLogger() << "Finished updateVision" << endl;
	Logger::theLogger() << "Start clearCaches" << endl;
	field.clearCaches();
	Logger::theLogger() << "Finished clearCaches" << endl;
	Logger::theLogger() << "Starting analyzeMap" << endl;
	state.analyzeMap();
	Logger::theLogger() << "Finished analyzeMap" << endl;
	Logger::theLogger() << "Starting buildSquads" << endl;
	buildSquads();
	Logger::theLogger() << "Finished buildSquads" << endl;
	Logger::theLogger() << "Starting makeMoves" << endl;
        makeMoves();
	Logger::theLogger() << "Finished makeMoves" << endl;
        endTurn();
    }
};

void Bot::printSquad(const int& squad_id)  {
    Logger::theLogger() << " squad_id:" << squad_id << ",squad_size:" 
			<< squadList[squad_id].size() << endl;
    Logger::theLogger() << "Ant List:" ;
	    
    for(vector<Location>::const_iterator it = squadList[squad_id].begin();
	it!=squadList[squad_id].end();it++) {
	Logger::theLogger() << "(" << it->row << "," << it->col << "," << state.grid[it->row][it->col].ant << ")" <<  endl;
    }
    Logger::theLogger() << endl;
}

// go through list of ants and group nearby ants in squads
// A squad can be a single ant or upto 10 ants. Each squad
// is scheduled as a unit and moved as unit.
void Bot::buildSquads() {
    clearSquads();
    processedAnts.clear();
    int squad_id =0;
    int SQUAD_SIZE=1;
    int MAX_SQUADS= state.ants.size()/25;
    if (MAX_SQUADS>0) 
	SQUAD_SIZE=5;
    int num_real_squads = 0;
    Logger::theLogger() << "MAX_SQUADS: " << MAX_SQUADS<<"Squad Size:" << SQUAD_SIZE << endl;
    for (int i=0;i<state.ants.size();i++) {
	if (isInSquad(state.ants[i])) 
	    continue;//skip any ants that are already in squad
	if (num_real_squads>=MAX_SQUADS) {
	    SQUAD_SIZE=1;
	}
	
	squad_id++;
	squadList[squad_id].push_back(state.ants[i]);
	inSquad[state.ants[i]] = true;
	std::vector<Location> antList;
	state.findFriendlyAntsInRadius(state.ants[i],state.attackradius*2,antList);
	bool squad_created =false;
	for(std::vector<Location>::iterator it = antList.begin();
	    it!=antList.end();it++){

	    if (isInSquad(*it)) 
		continue;
	    
	    if (squadList[squad_id].size()<SQUAD_SIZE) {
		squadList[squad_id].push_back(*it);
		inSquad[*it] = true;
		squad_created = true;
	    }
	    else {
		break; //this squad is full.
	    }
	}
	if (squad_created)
	    num_real_squads++;
    }
}

bool Bot::isInSquad(const Location& loc) const  {
    if (inSquad.find(loc)!=inSquad.end()) 
	return true;
    return false;
}

void Bot::clearSquads() {
    inSquad.clear();
    squadList.clear();
}

void Bot::moveSquad(const int& squad_id) {
    Logger::theLogger() << "Moving Squad_id: " << squad_id << ", squad_size: " << squadList[squad_id].size() << endl;
    printSquad(squad_id);
    if (!squadHuntFood(squad_id)) 
	if (!squadHuntAnt(squad_id))
	    moveToFrontLine(squad_id);
    Logger::theLogger() << "Finished Moving Squad_id: " << squad_id << ", squad_size: " << squadList[squad_id].size() << endl;
}

bool Bot::moveAntTo(const Location& ant,const Location& target) {
    stack<int> path;
    int numNodesExplored = 0;
    
    if (state.findPath(ant,target,path,numNodesExplored)) {
	Location nLoc = state.getLocation(ant,path.top());
	if (state.grid[nLoc.row][nLoc.col].ant!=0) {
	    state.makeMove(ant,path.top());
	    path.pop();
	    return true;
	}
    }
    return false;
}

//returns a list of paths for each ant in squad to loc
PathQueue Bot::generateSquadMoves(vector<Location>::iterator start,
				  vector<Location>::iterator end,
				  const Location& loc) {
    PathQueue pq;
    for (vector<Location>::iterator it = start; it!=end;it++ ) {
	stack<int> path;
	int numNodesExplored = 0;
	state.findPath(*it,loc,path,numNodesExplored);
	pq.push(PathQueueEntry(*it,path));
    }
    return pq;
}

bool Bot::moveSquadTo(vector<Location>::iterator start,
		      vector<Location>::iterator end,
		      const Location& loc,int& shortestPathLen) {
    Logger::theLogger() <<"Moving Squad to : " << loc.row << "," << loc.col << endl;
    //generate all paths for units in squad
    PathQueue squadMoves = generateSquadMoves(start,end,loc);
    PathQueue squadMoveCopy;
    stack< PathQueueEntry > moveStack;
    while (!squadMoves.empty()) {
	//get the ant and path and make the move
	PathQueueEntry antPath = squadMoves.top();
	squadMoves.pop();
	if (antPath.path.empty() )
	    continue;
	Location nLoc = state.getLocation(antPath.antLoc,antPath.path.top());
	if (state.grid[nLoc.row][nLoc.col].ant!=0) {
	    state.mockMakeMove(antPath.antLoc,antPath.path.top());
	    moveStack.push(antPath);
	    squadMoveCopy.push(antPath);
	}
    }
    int battleResult = resolveBattle(loc) ;
    while (!moveStack.empty()) {
	PathQueueEntry antPath = moveStack.top();
	moveStack.pop();
	state.unmakeMockMove(antPath.antLoc,antPath.path.top());
    }
    if (battleResult>=0) {
	//now make all these moves
	bool first = true;
	while (!squadMoveCopy.empty()) {
	//get the ant and path and make the move
	    PathQueueEntry antPath = squadMoveCopy.top();
	    if (first) {
		shortestPathLen = antPath.path.size();
		first = false;
	    }
	    squadMoveCopy.pop();
	    Location nLoc = state.getLocation(antPath.antLoc,antPath.path.top());
	    if (state.grid[nLoc.row][nLoc.col].ant!=0) {
		state.makeMove(antPath.antLoc,antPath.path.top());
	    }
	}
	return true;
    }
    return false;
}

bool Bot::squadPotentialBasedMove(const int& squad_id) {
    int direction;    
    for(vector<Location>::iterator it = squadList[squad_id].begin();
	it!=squadList[squad_id].end();it++) {
	Location ant = *(it);
	if (field.higher(ant,direction)) {
	    Location nLoc = state.getLocation(ant,direction);
	    if (state.grid[nLoc.row][nLoc.col].ant!=0) {
		Logger::theLogger() << "PotentialBasedMove: ";
		Logger::theLogger() << "o " << ant.row << " " << ant.col << " " << CDIRECTIONS[direction] << endl;
		state.makeMove(ant,direction);
		field.visited(ant);
	    }
	}
    }
    return true;
}

bool Bot::squadHuntAnt(const int& squad_id) {
//Try to find a closest ant and move towards it.
    Location antLoc = *(squadList[squad_id].begin());
    Location enemyAntLoc;
    stack<int> path;
    int numNodesExplored=0;
    if (state.findClosestEnemyAnt(antLoc,enemyAntLoc,path,numNodesExplored)) {
	Logger::theLogger() << "Ant at: " << antLoc.row << "," <<antLoc.col << endl;
	Logger::theLogger() << "Found enemyAnt: " << enemyAntLoc.row << "," << enemyAntLoc.col << endl;
	Logger::theLogger() << "numNodesExplored:" << numNodesExplored << endl;
	if (!path.empty()) {
	    Location nLoc = state.getLocation(antLoc,path.top());
	    if (nLoc!=enemyAntLoc && state.grid[nLoc.row][nLoc.col].ant!=0) {
		int shortestPathLen;
		if (moveSquadTo(squadList[squad_id].begin(),squadList[squad_id].end(),enemyAntLoc,shortestPathLen)) {
		    state.grid[enemyAntLoc.row][enemyAntLoc.col].tracking+=1;
		    return true;
		}
		else
		    return false;
	    }
	}
    }
    return false;
}

bool Bot::squadHuntFood(const int& squad_id) {
    //The first ant in the squad is the leader.
    Location leaderAnt = *(squadList[squad_id].begin());
    Location foodLoc;
    stack<int> path;
    int numNodesExplored = 0;
    if (state.findClosestFood(leaderAnt,foodLoc,path,numNodesExplored)) {
	if (!path.empty()) {
	    Logger::theLogger() << "Squad at: " << leaderAnt.row << "," <<leaderAnt.col << endl;
	    Logger::theLogger() << "Found food: " << foodLoc.row << "," << foodLoc.col << endl;
	    Logger::theLogger() << "numNodesExplored:" << numNodesExplored << endl;
	    if (state.grid[foodLoc.row][foodLoc.col].tracking>0) {
		int maxPathLength = state.foodTrackingPathLengths[foodLoc];
		if (maxPathLength > path.size()) {
		    Location nLoc = state.getLocation(leaderAnt,path.top());
		    if (nLoc!=foodLoc && state.grid[nLoc.row][nLoc.col].ant!=0) {
			int shortestPathLen;
			if (moveSquadTo(squadList[squad_id].begin(),squadList[squad_id].end(),foodLoc,shortestPathLen)) {
			    state.grid[foodLoc.row][foodLoc.col].tracking+=1;
			    state.foodTrackingPathLengths[foodLoc] = shortestPathLen;
			    return true;
			}
			else
			    return false;
		    }
		}
		else {
		    return false;
		}
	    }
	    else { //no other squad is tracking this food
		Location nLoc = state.getLocation(leaderAnt,path.top());
		if (nLoc!=foodLoc && state.grid[nLoc.row][nLoc.col].ant!=0) {
		    int shortestPathLen;
		    if (moveSquadTo(squadList[squad_id].begin(),squadList[squad_id].end(),foodLoc,shortestPathLen)) {
			state.grid[foodLoc.row][foodLoc.col].tracking+=1;
			state.foodTrackingPathLengths[foodLoc] = shortestPathLen;
			return true;
		    }
		}
	    }
	}
    }
    return false;
}

void Bot::moveToFrontLine(const int& squad_id) {
    Logger::theLogger() << "Moving To FrontLine" << endl;
    double min_dist =DBL_MAX;
    Location closestFrontLoc =squadList[squad_id][0];
    for (int i =0; i < squadList[squad_id].size();i++)  {
	for(int j=0;j<state.frontLine.size();j++) {
	    Location frontLoc = state.frontLine[j];
	    if (state.grid[frontLoc.row][frontLoc.col].tracking>3) { 
		continue;
	    }
	    double dist = state.distance(squadList[squad_id][i],frontLoc);
	    if (dist<min_dist) {
		closestFrontLoc=frontLoc;
		min_dist = dist;
	    }
	}
    }
    if (closestFrontLoc == squadList[squad_id][0]) 
	return;
    state.grid[closestFrontLoc.row][closestFrontLoc.col].tracking+=1;
    int shortestPathLen;
    moveSquadTo(squadList[squad_id].begin(),squadList[squad_id].end(),closestFrontLoc,shortestPathLen);
}

//Make a random move, 
//TODO: Not very random, need to shuffle directions before looping.
void Bot::randomMove(int ant) {
    for(int d=0; d<TDIRECTIONS; d++)
    {
	Location loc = state.getLocation(state.ants[ant], d);
	
	if(!state.grid[loc.row][loc.col].isWater && (state.grid[loc.row][loc.col].ant==-1))
	{
	    Logger::theLogger() << "Random Move: " << loc.row << "," << loc.col << endl;
	    state.makeMove(state.ants[ant], d);
	    break;
	}
    }
}

//return True if there is any enemy ant within attackradius of the location
bool Bot::isLocationContested(const Location& nLoc) const {
    
}

//resolve battle at nLoc. Expands battle to encompass all ants affecting
//each other and returns 1 if its overall in our favour, 0 if all sides
//lose equal number, -1 if its against us.
int Bot::resolveBattle(const Location& nLoc) {
    //Initialize a battle grid with 0 dmg done to all squares, any squares
    vector< vector<double> > battleGrid(state.rows, vector<double> (state.cols,0));

    queue<Location> antQueue;
    vector< vector<bool> > visited(state.rows,vector<bool>(state.cols,0));

    antQueue.push(nLoc);
    vector<Location> allAnts;
    while (!antQueue.empty()) {
	//We find all neighbouring unvisited ants and add them to  queue
	//for each ant we expand the set of affected ants. Till we have a list
	//of ants which impact each other.
	Location ant = antQueue.front();
	antQueue.pop();
	visited[ant.row][ant.col] = true;
	vector<Location> nearbyAnts;
	state.findAntsInRadius(nLoc,state.attackradius,nearbyAnts);
	allAnts.push_back(ant);
	int nEnemyAnts = 0;
	int nFriendlyAnts = 0;
	vector<Location> enemyAnts;
	for(int i=0;i<nearbyAnts.size();i++) {
	    //add all new ants discovered to the queue for expansion
	    if (!visited[nearbyAnts[i].row][nearbyAnts[i].col]) {
		antQueue.push(nearbyAnts[i]);
	    }
	    if (state.grid[nearbyAnts[i].row][nearbyAnts[i].col].ant == 
		state.grid[ant.row][ant.col].ant) {
		nFriendlyAnts++;
	    } else {
		nEnemyAnts++;
		enemyAnts.push_back(nearbyAnts[i]);
	    }
	}
	//do battle for all ants not owned by current ant's owner
	//distribute 1 dmg to all the others
	if (enemyAnts.size()!=0) {
	    double dmg_to_distribute = 1.0/enemyAnts.size();
	    for(int i=0;i<enemyAnts.size();i++) {
		battleGrid[enemyAnts[i].row][enemyAnts[i].col]+=dmg_to_distribute;
	    }
	}
    }

    //At this point we should have a battleGrid with all dmg calculations
    //for all ants affected. Now its just a matter of calculating overall
    //ants lost/killed and evaluate if the move is worth it.
    map<int,int> playerAntLosses;
    for(vector<Location>::const_iterator it=allAnts.begin();it!=allAnts.end();it++) {
	if (battleGrid[it->row][it->col]>0.9999) {
	    playerAntLosses[state.grid[it->row][it->col].ant] +=1;
	}
    }   

    int myLosses = playerAntLosses[0] ;
    if (myLosses==0) {
	return 1;
    }
    int enemyLosses =0 ;
    for(map<int,int>::const_iterator it = playerAntLosses.begin();
	it!=playerAntLosses.end();it++) {
	if (it->first!=0) {
	    enemyLosses+=it->second;
	}
    }

    if (myLosses>enemyLosses) {
	return -1;
    }
    else if (myLosses==enemyLosses) {
	return 0;
    } else {
	return 1;
    }
}

//Try to find a closest food and move towards it.
//by other ants.
bool Bot::huntFood(int ant) {
    Location antLoc = state.ants[ant];
    Location foodLoc;
    stack<int> path;
    int numNodesExplored=0;
    if (state.findClosestFood(antLoc,foodLoc,path,numNodesExplored)) {
	if (!path.empty()) {
	    Logger::theLogger() << "Ant at: " << antLoc.row << "," <<antLoc.col << endl;
	    Logger::theLogger() << "Found food: " << foodLoc.row << "," << foodLoc.col << endl;
	    Logger::theLogger() << "numNodesExplored:" << numNodesExplored << endl;
	    //Now check if the food is already being tracked and if
	    //we try and acquire only if one of the following conditions holds true
	    // a) current max path length to the food is > path length for this ant 
	    // TODO b) enemy ant has a shorter path than current max path length
	    if (state.grid[foodLoc.row][foodLoc.col].tracking>0) {
		int maxPathLength = state.foodTrackingPathLengths[foodLoc];
		if (maxPathLength > path.size()) {
		    Location nLoc = state.getLocation(state.ants[ant],path.top());
		    if (nLoc!=foodLoc && state.grid[nLoc.row][nLoc.col].ant!=0) {
			state.grid[foodLoc.row][foodLoc.col].tracking+=1;
			state.foodTrackingPathLengths[foodLoc] = path.size();
			state.makeMove(state.ants[ant],path.top());
			path.pop();
			return true;
		    }
		}
		else {
		    return false;
		}
	    }
	    else {
		Location nLoc = state.getLocation(state.ants[ant],path.top());
		if (nLoc!=foodLoc && state.grid[nLoc.row][nLoc.col].ant!=0) {
		    state.grid[foodLoc.row][foodLoc.col].tracking+=1;
		    state.foodTrackingPathLengths[foodLoc] = path.size();
		    state.makeMove(state.ants[ant],path.top());
		    path.pop();
		    return true;
		}
	    }
	    return false;
	}
	else {
	    Logger::theLogger() << "Oops found food but path is empty" << endl;
	}
    }
    return false;
}

//Try to find a closest ant and move towards it.
bool Bot::huntAnts(int ant) {
    Location antLoc = state.ants[ant];
    Location enemyAntLoc;
    stack<int> path;
    int numNodesExplored=0;
    if (state.findClosestEnemyAnt(antLoc,enemyAntLoc,path,numNodesExplored)) {
	Logger::theLogger() << "Ant at: " << antLoc.row << "," <<antLoc.col << endl;
	Logger::theLogger() << "Found enemyAnt: " << enemyAntLoc.row << "," << enemyAntLoc.col << endl;
	Logger::theLogger() << "numNodesExplored:" << numNodesExplored << endl;
	if (!path.empty()) {
	    Location nLoc = state.getLocation(state.ants[ant],path.top());
	    if (nLoc!=enemyAntLoc && state.grid[nLoc.row][nLoc.col].ant!=0) {
		//Now make this move only if its helpful
		state.mockMakeMove(state.ants[ant],path.top());
		int battleResult = resolveBattle(nLoc);
		state.unmakeMockMove(state.ants[ant],path.top());
		if (battleResult>=0) {
		    Logger::theLogger() <<"Victorious battle" << endl;
		    state.grid[enemyAntLoc.row][enemyAntLoc.col].tracking+=1;
		    state.makeMove(state.ants[ant],path.top());
		    path.pop();
		    return true;
		}
		else {
		    //run in reverse direction
		    Logger::theLogger() <<"Losing battle, Try to flee to closest friendly ant" << endl;
		    Logger::theLogger() <<"Original Move:" ;
		    Logger::theLogger() << "o " << state.ants[ant].row << " " << state.ants[ant].col << " " << CDIRECTIONS[path.top()] << endl;
		    Location friendlyAntLoc;
		    stack<int> pathToFriendly;
		    int pathLen;
		    if (state.findClosestFriendlyAnt(state.ants[ant],friendlyAntLoc,pathToFriendly,pathLen)) {
			if (!path.empty()) {
			    Location nextLoc = state.getLocation(state.ants[ant],pathToFriendly.top());
			    if (nextLoc!=nLoc && state.grid[nextLoc.row][nextLoc.col].ant<0) {
				Logger::theLogger() << "Path to friendly: " ;
				Logger::theLogger() << "o " << state.ants[ant].row << " " << state.ants[ant].col << " " << CDIRECTIONS[pathToFriendly.top()] << endl;
				state.makeMove(state.ants[ant],pathToFriendly.top());
				pathToFriendly.pop();
				return true;
			    }
			}
		    }
		    else {
			Logger::theLogger() <<"Can't flee way blocked,stay" << endl;
			return true;
		    }
		}
	    }
	    return true;
	}
	else {
	    Logger::theLogger() << "Oops found an enemyAnt but path is empty" << endl;
	}
    }
    return false;
}

//void Bot::potentialBasedMove

bool Bot::potentialBasedMove(const Location& ant) {
    int direction;    
    if (field.higher(ant,direction)) {
	Location nLoc = state.getLocation(ant,direction);
	if (state.grid[nLoc.row][nLoc.col].ant!=0) {
	    Logger::theLogger() << "PotentialBasedMove: ";
	    Logger::theLogger() << "o " << ant.row << " " << ant.col << " " << CDIRECTIONS[direction] << endl;
	    state.makeMove(ant,direction);
	    field.visited(ant);
	    return true;
	}
    }
    return false;
}

//makes the bots moves for the turn
void Bot::makeMoves()
{
    Logger::theLogger() << "turn " << state.turn << ":" << endl;
    Logger::theLogger() << state << endl;

//     //picks out moves for each ant
//     for(int ant=0; ant<(int)state.ants.size(); ant++)
//     {
// 	if (!huntFood(ant))
// 	    if (!huntAnts(ant))
// 		potentialBasedMove(state.ants[ant]);
//     }

    //pick out moves per squad
    for (map< int, vector<Location> >::iterator it=squadList.begin();
	 it!=squadList.end();
	 it++) {
	moveSquad(it->first);
    }
    Logger::theLogger() << "Move time taken: " << state.timer.getTime() << "ms" << endl << endl;
};

//finishes the turn
void Bot::endTurn()
{
    if(state.turn > 0)
        state.reset();
    state.turn++;

    cout << "go" << endl;
};
